package Atop100.dp;
//爬楼梯

import Atop100.listNode.Class2;
import listNodePractice.ListNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Class70 {
//TODO:2023/10/27 最简单原始的方法
    public int climbStairs(int n) {
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }

        return dp[n];
    }
//TODO:2023/10/27  chatgpt 给出的答案
        public static int countWaysToClimbStairs(int n) {
            if (n <= 0) {
                return 0;
            } else if (n <= 2) {
                return n;
            } else if (n == 3) {
                return 4;
            }
            int[] ways = new int[n + 1];
            ways[0] = 0;
            ways[1] = 1;
            ways[2] = 2;
            ways[3] = 4;
            for (int i = 4; i <= n; i++) {
                ways[i] = ways[i - 1] + ways[i - 2] + ways[i - 3];
            }
            return ways[n];
        }

        public static List<List<Integer>> enumerateWaysToClimbStairs(int n) {
            List<List<Integer>> result = new ArrayList<>();
            List<Integer> currentPath = new ArrayList<>();
            enumerateWaysToClimbStairsHelper(n, currentPath, result);
            return result;
        }

        private static void enumerateWaysToClimbStairsHelper(int n, List<Integer> currentPath, List<List<Integer>> result) {
            if (n == 0) {
                result.add(new ArrayList<>(currentPath));
            } else if (n > 0) {
                for (int i = 1; i <= 3; i++) {
                    currentPath.add(i);
                    enumerateWaysToClimbStairsHelper(n - i, currentPath, result);
                    currentPath.remove(currentPath.size() - 1);
                }
            }
        }


        //TODO:2023/10/27 结合chatgpt 给出的答案，可以思考爬楼梯问题 也可以理解为给出 数 也就是每次可以爬的楼梯数，求爬完n级台阶的组合数 ，里面每次可以爬的次数

       List<List<Integer>>  result=new ArrayList<>();
       List<Integer> path=new LinkedList<>();

       public int climbStairs1(int n) {
           backtracking(0,n,3);
           return  result.size();
        }

        public  void  backtracking(int sum,int n,int k){
           if(sum>n){
               return;
           }
           if (sum==n){
               result.add(new ArrayList<>(path));
           }
           for (int i = 1; i <=k ; i++) {
              sum+=i;
              if (sum<=n){
                  path.add(i);
                  backtracking(sum,n,k);
                  path.remove(path.size()-1);
                  sum-=i;
              }
            }
        }



    public static void main(String[] args) {
        int n = 3;
        int ways = countWaysToClimbStairs(n);
        System.out.println("爬 " + n + " 级台阶的方式数量为: " + ways);

        List<List<Integer>> allWays = enumerateWaysToClimbStairs(n);
        System.out.println("列举出所有方式:");
        for (List<Integer> way : allWays) {
            System.out.println(way);
        }

        Class70 class70 = new Class70();
        int i = class70.climbStairs1(3);
        System.out.println(i);

    }


}


